For several years now, online map services are widespread on the world-wide web, and the popularity of such services in hand-held devices is rapidly growing. Since map services are accessible to many novice users, they should allow easy formulation of queries that specify complex needs, such as a route search, i.e., finding a route that goes via some specified types of geographical entities.
In a traditional search over the world-wide web, users usually specify conditions in the form of a set of keywords. The result of a search is a ranked list of documents that satisfy the search conditions. The paradigm of a traditional search is, however, unsuitable for geographic search, because users need to actually visit the entities of the result. Traditional ranking methods ignore the location of the entities, the distance of entities from the location of the user and the distance of relevant entities from other relevant entities. Consequently, visiting geographical objects in an order that is the result of a traditional search may produce a long travel, whereas there is likely to be a much shorter route that also satisfies the user needs.
A paradigm of route search is introduced. In a route search, the user provides keywords that specify the entities she wants to visit and a target destination. The source location is either provided by the user or discovered automatically, e.g., using a GPS device. The goal is to find a route that starts at the source location, ends at the target location and goes through entities that are relevant to the search.